package BinaryTreeExer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-20
 * Time: 18:18
 */









/**
 * 解法一：时间复杂度为O（N^2）
 */

/**
 时间复杂度为O（N^2,N的平方）；因为我们求高度自己实现的函数getHeight，是先遍历放到
 最后一次二叉树再，逐一返回，当（isBalanced(root.left) &&  isBalanced(root.right);//去递归每一棵树的左右子树）时会重复去算高度
 */
public class BinaryTreeExercise1 {

    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        //判断二叉树节点是平衡树
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight - rightHeight) < 2 &&
                isBalanced(root.left) &&  isBalanced(root.right);//去递归每一棵树的左右子树


    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //递归遍历左右树高度，遍历到root == null，再返回
        int leftTreeHeight = getHeight(root.left);
        int rightTreeHeight = getHeight(root.right);

        return Math.max(leftTreeHeight, rightTreeHeight) + 1;
    }
}







/**
 解法二：时间复杂度为O(N),
 方法 : 在递归，节点返回时，顺便判断属不属于平衡二叉树
 */

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }

        return getHeight(root) >= 0;
    }

    public  int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //递归遍历左右树高度，遍历到root == null，再返回
        int leftTreeHeight = getHeight(root.left);
        if (leftTreeHeight < 0) {
            return -1;
        }


        int rightTreeHeight = getHeight(root.right);

        /**
         这里注意当二叉树遍历整棵树的最右边时，右边会返回-1，会破坏右边二叉树返回时的高度
         所以，rightTreeHeight的值要判断；如果等于-1，就不可以向上返回

         限制：（rightTreeHeight>=0）

         */
        if (rightTreeHeight >= 0 && Math.abs(leftTreeHeight - rightTreeHeight) <= 1) {
            //是平衡二叉树,返回左右树做大值加1
            return Math.max(leftTreeHeight, rightTreeHeight) + 1;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {

    }
}
